{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Can Place Flowers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canPlaceFlowers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #种花问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。</p>\n",
    "\n",
    "<p>给你一个整数数组&nbsp;<code>flowerbed</code> 表示花坛，由若干 <code>0</code> 和 <code>1</code> 组成，其中 <code>0</code> 表示没种植花，<code>1</code> 表示种植了花。另有一个数&nbsp;<code>n</code><strong> </strong>，能否在不打破种植规则的情况下种入&nbsp;<code>n</code><strong>&nbsp;</strong>朵花？能则返回 <code>true</code> ，不能则返回 <code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>flowerbed = [1,0,0,0,1], n = 1\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>flowerbed = [1,0,0,0,1], n = 2\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= flowerbed.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>flowerbed[i]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "\t<li><code>flowerbed</code> 中不存在相邻的两朵花</li>\n",
    "\t<li><code>0 &lt;= n &lt;= flowerbed.length</code></li>\n",
    "</ul>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [can-place-flowers](https://leetcode.cn/problems/can-place-flowers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [can-place-flowers](https://leetcode.cn/problems/can-place-flowers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,0,0,1]\\n1', '[1,0,0,0,1]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        N = len(flowerbed)\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while i < N:\n",
    "            if (i==0 or flowerbed[i-1] ==0) and (i==N-1 or flowerbed[i+1]==0) and flowerbed[i]==0:\n",
    "                flowerbed[i] = 1\n",
    "                ans += 1\n",
    "                i+=2\n",
    "            else:\n",
    "                i+=1\n",
    "        if ans >=n:\n",
    "            return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed, n):\n",
    "        \"\"\"\n",
    "        :type flowerbed: List[int]\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        length = len(flowerbed)\n",
    "        if n == 0:\n",
    "            return True\n",
    "        for i in range(length):\n",
    "            if flowerbed[i] == 1:\n",
    "                continue\n",
    "            else:\n",
    "                if i == 0:\n",
    "                    pre = 0\n",
    "                else:\n",
    "                    pre = flowerbed[i-1]\n",
    "                \n",
    "                if i == length-1:\n",
    "                    nex = 0\n",
    "                else:\n",
    "                    nex = flowerbed[i+1]\n",
    "            if pre == 0 and nex == 0:\n",
    "                n -= 1\n",
    "                flowerbed[i] = 1\n",
    "            if n == 0:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed, n):\n",
    "        \"\"\"\n",
    "        :type flowerbed: List[int]\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        flowerbed.insert(0,0)\n",
    "        flowerbed.insert(0,1)\n",
    "        flowerbed.append(0)\n",
    "        flowerbed.append(1)\n",
    "        print(flowerbed)\n",
    "        num = 0\n",
    "        for item in flowerbed:\n",
    "            if item == 0:\n",
    "                num += 1\n",
    "            else:\n",
    "                num = 0\n",
    "            if num == 3:\n",
    "                res += 1\n",
    "                num = 1\n",
    "        return (res >= n)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed, n):\n",
    "        flowerbed.insert(0, 0)\n",
    "        flowerbed.append(0)\n",
    "        count = 0\n",
    "        for f in flowerbed:\n",
    "            if f == 0:\n",
    "                count += 1\n",
    "            else:\n",
    "                count = 0\n",
    "            if count == 3:\n",
    "                n -= 1\n",
    "                count = 1\n",
    "            if n == 0:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed, n):\n",
    "        \"\"\"\n",
    "        :type flowerbed: List[int]\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        count = 0\n",
    "        flowerbed = [0] + flowerbed + [0]\n",
    "        for i in range(1, len(flowerbed)-1):\n",
    "            if flowerbed[i] == 0 and flowerbed[i-1] == 0 and flowerbed[i+1] == 0:\n",
    "                count += 1\n",
    "                flowerbed[i] = 1\n",
    "        \n",
    "        return n <= count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        keyi=0\n",
    "        if len(flowerbed)==1:\n",
    "            if flowerbed[0]==0:\n",
    "                keyi+=1\n",
    "        else:  \n",
    "            if flowerbed[0]==0 and flowerbed[1]==0:\n",
    "                flowerbed[0]=1\n",
    "                keyi+=1\n",
    "            if  flowerbed[len(flowerbed)-1]==0 and flowerbed[len(flowerbed)-2]==0:\n",
    "                flowerbed[len(flowerbed)-1]=1\n",
    "                keyi+=1\n",
    "            for i in range(1,len(flowerbed)-1):\n",
    "                if flowerbed[i]==0:\n",
    "                    if flowerbed[i-1]!=1 and flowerbed[i+1]!=1:\n",
    "                        keyi+=1\n",
    "                        flowerbed[i]=1\n",
    "        if keyi>=n:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed, n):\n",
    "        \"\"\"\n",
    "        :type flowerbed: List[int]\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # _max=len(seats)\n",
    "        if len(flowerbed)==0:# []\n",
    "            return False\n",
    "        elif len(flowerbed)==1:\n",
    "            if flowerbed[0]==1 and n==1:#[1] 1\n",
    "                return False\n",
    "            elif flowerbed[0]==1 and n==0:#[1] 0\n",
    "                return True\n",
    "            elif flowerbed[0]==0 and n<=1:#[0] 0\n",
    "                return True\n",
    "            elif flowerbed[0]==0 and n>1:#[0] 1\n",
    "                return False\n",
    "        if max(flowerbed)==0:#[0,0,0,...]\n",
    "            if len(flowerbed)%2==0:\n",
    "                res1=int(len(flowerbed)/2)\n",
    "            else:\n",
    "                res1=int((len(flowerbed)+1)/2)\n",
    "            if res1>=n:\n",
    "                return True\n",
    "            else:return False\n",
    "        _min=0\n",
    "        for i in range(len(flowerbed)):\n",
    "            if flowerbed[i]==1:\n",
    "                _min=i\n",
    "                break\n",
    "        s=[]\n",
    "        _s=[]\n",
    "        qian=0;hou=0\n",
    "        if flowerbed[0]==0:\n",
    "            qian=_min-1\n",
    "        # print('qian',qian)\n",
    "        \n",
    "        for i in range(1,len(flowerbed)):\n",
    "            if flowerbed[i]==1 and i>_min:\n",
    "                # _max=i\n",
    "                s.append([_min,i])\n",
    "                _s.append(i-_min-1)\n",
    "                _min=i\n",
    "            elif flowerbed[i] ==1:\n",
    "                _min=i\n",
    "        # print('_min',_min)\n",
    "        if flowerbed[-1]==0:\n",
    "            hou=len(flowerbed)-1-_min-1\n",
    "        # print('hou',hou)\n",
    "        \n",
    "        zhong=0\n",
    "        num_z=0\n",
    "        if len(_s)>0:\n",
    "            num_z=0\n",
    "            for i in range(len(_s)):\n",
    "                nu=0\n",
    "                if _s[i]>2:\n",
    "                    if _s[i]%2 ==0:\n",
    "                        nu=int((_s[i]-2)/2)\n",
    "                    else:\n",
    "                        nu=int((_s[i]-1)/2)\n",
    "                num_z+=nu\n",
    "        num_q=0;num_h=0\n",
    "        if qian+1>1:\n",
    "            if (qian+1)%2==0:\n",
    "                num_q=int((qian+1)/2)\n",
    "            else:\n",
    "                num_q=int((qian+1-1)/2)\n",
    "                \n",
    "        if hou+1>1:\n",
    "            if (hou+1)%2==0:\n",
    "                num_h=int((hou+1)/2)\n",
    "            else:\n",
    "                num_h=int((hou+1-1)/2)\n",
    "        # print('num_q',num_q)\n",
    "        # print('num_z',num_z)\n",
    "        # print('num_h',num_h)\n",
    "        res=num_q+num_z+num_h\n",
    "        if res>=n:\n",
    "            return True\n",
    "            # print(True)\n",
    "        else:\n",
    "            return False\n",
    "            # print(False)\n",
    "        # print('res',res)\n",
    "        # # if zhong\n",
    "        # # print('cou',cou)\n",
    "        # print('zhong',zhong)\n",
    "        print(s)\n",
    "        print(_s)\n",
    "        # return max(qian,int(zhong),hou)+1\n",
    "\n",
    "        # print(cou)\n",
    "        # print(_max)\n",
    "        # print(_min)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed, n):\n",
    "        \"\"\"\n",
    "        :type flowerbed: List[int]\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        lst = []\n",
    "        lst2 = []\n",
    "        number=0\n",
    "        for i in range(len(flowerbed)):\n",
    "            if flowerbed[i] == 1:\n",
    "                if i not in lst:\n",
    "                    lst.append(i)\n",
    "                    lst.append(i + 1)\n",
    "                    lst.append(i - 1)\n",
    "        for i in range(len(flowerbed)):\n",
    "            if i not in lst:\n",
    "                if i+1 not in lst2 and i-1 not in lst2:\n",
    "                    lst2.append(i)\n",
    "        number=len(lst2)\n",
    "        if n>number:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self,flowerbed, n):\n",
    "        \"\"\"\n",
    "        :type flowerbed: List[int]\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if flowerbed==[0]:\n",
    "            if n<=1:\n",
    "                return True\n",
    "            return False\n",
    "        if flowerbed==[1]:\n",
    "            if n==0:\n",
    "                return True\n",
    "            return False\n",
    "                \n",
    "        count=0\n",
    "        string = ''.join([str(i) for i in flowerbed])\n",
    "        lst = string.split('1')\n",
    "        if len(lst)==1:\n",
    "            if lst[0]=='0' and n<=1:\n",
    "                return True\n",
    "            elif lst[0]=='0' and n>1:\n",
    "                return False\n",
    "            else:\n",
    "                count =(len(lst[0])-1)//2+1\n",
    "                if count>=n:\n",
    "                    return True\n",
    "                return False\n",
    "        if '0' in lst[0]:\n",
    "            if len(lst[0])==1:\n",
    "                count+=0\n",
    "            else:\n",
    "                count+=(len(lst[0])-1)//2+1\n",
    "        if '0' in lst[-1]:\n",
    "            if len(lst[-1])==1:\n",
    "                count+=0\n",
    "            else:\n",
    "                count+=(len(lst[-1])-1)//2+1\n",
    "        if lst[1:-1]!=[]:\n",
    "            for i in range(1,len(lst)-1):\n",
    "                if lst[i]!='':\n",
    "                    count+=(len(lst[i])-1)//2\n",
    "        if count>=n:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        f = [0] + flowerbed + [0]\n",
    "        i = 1\n",
    "        count = 0\n",
    "        while i < len(flowerbed)+1:\n",
    "            if f[i-1] == f[i] == f[i+1] == 0:\n",
    "                count += 1\n",
    "                i += 2\n",
    "            else:\n",
    "                i += 1\n",
    "        return count >= n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        count = 0\n",
    "        pre = flowerbed[0]\n",
    "        nums = 0 if pre else 2\n",
    "        for i in range(1, len(flowerbed)):\n",
    "            if pre == 0 and flowerbed[i] == 0:\n",
    "                nums += 1\n",
    "            elif pre == 0 and flowerbed[i] == 1:\n",
    "                count += (nums - 1) // 2\n",
    "                nums = 0\n",
    "                pre = 1\n",
    "            else:\n",
    "                nums = 1\n",
    "                pre = 0\n",
    "        \n",
    "        if nums >= 2:\n",
    "            count += nums // 2\n",
    "\n",
    "        return count >= n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        i, num = 0, len(flowerbed)\n",
    "        while i < num and n > 0:\n",
    "            if flowerbed[i] == 0 and (i == num - 1 or flowerbed[i + 1] == 0):\n",
    "                n -= 1\n",
    "                flowerbed[i] = 1\n",
    "                i += 1\n",
    "            elif flowerbed[i] == 1:\n",
    "                i += 1\n",
    "            i += 1\n",
    "        return n == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        length = len(flowerbed)\n",
    "        k = 0\n",
    "        i = 1\n",
    "        if length == 1:\n",
    "            if flowerbed[0] == 0:\n",
    "                k += 1\n",
    "            if k >= n :\n",
    "                return True\n",
    "            else:\n",
    "                return False   \n",
    "        if flowerbed[0] == flowerbed[1]:\n",
    "            k += 1\n",
    "            flowerbed[0] = 1\n",
    "            while i >= 1 and i < length - 1:  \n",
    "                if flowerbed[i-1] == flowerbed[i] and flowerbed[i] == flowerbed[i+1] and flowerbed[i] == 0:\n",
    "                    flowerbed[i] = 1\n",
    "                    k += 1\n",
    "                    i += 2\n",
    "                else :\n",
    "                    i += 1\n",
    "            if flowerbed[-1] == flowerbed[-2] and flowerbed[-1] == 0:\n",
    "                flowerbed[-1] == 1\n",
    "                k += 1\n",
    "            if k >= n :\n",
    "                return True\n",
    "            else:\n",
    "                return False        \n",
    "        else: \n",
    "            while i >= 1 and i < length - 1:  \n",
    "                if flowerbed[i-1] == flowerbed[i] and flowerbed[i] == flowerbed[i+1] and flowerbed[i] == 0:\n",
    "                    flowerbed[i] = 1\n",
    "                    k += 1\n",
    "                    i += 2\n",
    "                else :\n",
    "                    i += 1\n",
    "            if flowerbed[-1] == flowerbed[-2] and flowerbed[-1] == 0:\n",
    "                flowerbed[-1] == 1\n",
    "                k += 1\n",
    "            if k >= n :\n",
    "                return True\n",
    "            else:\n",
    "                return False        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        num = 0\n",
    "        size = len(flowerbed)\n",
    "        if size == 0:\n",
    "            return False\n",
    "        if size == 1:\n",
    "            if flowerbed[0] == 0 and n == 0:\n",
    "                return True\n",
    "            elif flowerbed[0] == 0 and n == 1:\n",
    "                return True\n",
    "            elif flowerbed[0] == 1 and n == 0:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        for step in range(size):\n",
    "            if step == 0:\n",
    "                if flowerbed[step+1] == 0 and flowerbed[step] == 0:\n",
    "                    flowerbed[step] = 1\n",
    "                    num = num + 1\n",
    "                    print(\"0 %d\"%num)\n",
    "            elif step == size - 1:\n",
    "                if flowerbed[step-1] == 0 and flowerbed[step] == 0:\n",
    "                    flowerbed[step] = 1\n",
    "                    num = num + 1\n",
    "                    print(\"%d %d\"%(size - 1, num)) \n",
    "            else:\n",
    "                if flowerbed[step+1] == 0 and flowerbed[step-1] == 0 and flowerbed[step] == 0:\n",
    "                    flowerbed[step] = 1               \n",
    "                    num = num + 1\n",
    "                    print(\"%d %d\"%(step, num))\n",
    "        if num >= n:\n",
    "            return True\n",
    "        else:\n",
    "            return False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 1. 找1，计算当前1(cur)和上一个1(pre)之间间隔0的个数interval\n",
    "# 2. 根据0的个数计算可种花的数目，叠加至结果 res += (interval - 1) // 2（2个0->0,3个0->1）\n",
    "# 3. 开头情况（pre的初值）：001...等效于(10)001...，pre取-2\n",
    "# 4. 结尾情况（cur的最后取值）：...100相当于...100(01)，cur取len + 1\n",
    "\n",
    "class Solution:\n",
    "    def flowers_between(self, left, right):\n",
    "        interval = right - left - 1\n",
    "        return (interval - 1) // 2\n",
    "    \n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        res = 0\n",
    "        pre = -2\n",
    "        for cur in range(len(flowerbed)):\n",
    "            if flowerbed[cur] != 1:\n",
    "                continue\n",
    "            res += self.flowers_between(pre, cur)\n",
    "            pre = cur\n",
    "\n",
    "        # 补上最后一个1右侧的花\n",
    "        res += self.flowers_between(pre, len(flowerbed) + 1)\n",
    "\n",
    "        return res >= n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        tem_list = [0] + flowerbed + [0]\n",
    "        num = len(tem_list)\n",
    "        k = 0\n",
    "        for i in range(1, num-1):\n",
    "            if tem_list[i] == 0 and tem_list[i-1] == 0 and tem_list[i+1] == 0 :\n",
    "                tem_list[i] = 1\n",
    "                k+=1\n",
    "        return(k >= n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        m = 0\n",
    "        s = 0\n",
    "        if len(flowerbed) == 1:\n",
    "            if flowerbed[0] == 0:\n",
    "                m = 1\n",
    "            else:\n",
    "                m = 0\n",
    "        else:\n",
    "            while s < len(flowerbed):\n",
    "                if flowerbed[s] == 1:\n",
    "                    s += 1\n",
    "                else:\n",
    "                    if s == 0:\n",
    "                        if flowerbed[s + 1] == 0:\n",
    "                            flowerbed[s] = 1\n",
    "                            m += 1\n",
    "                            s += 1\n",
    "                        else:\n",
    "                            s += 1\n",
    "                    elif s == len(flowerbed) - 1:\n",
    "                        if flowerbed[s - 1] == 0:\n",
    "                            flowerbed[s] = 1\n",
    "                            m += 1\n",
    "                            s += 1\n",
    "                        else:\n",
    "                            s += 1\n",
    "                    else:\n",
    "                        if flowerbed[s - 1] == 0 and flowerbed[s + 1] == 0:\n",
    "                            flowerbed[s] = 1\n",
    "                            m += 1\n",
    "                            s += 1\n",
    "                        else:\n",
    "                            s += 1\n",
    "\n",
    "        if m >= n:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        flowerbed = [0]+ flowerbed\n",
    "        flowerbed = flowerbed+[0]\n",
    "        for i in range(1,len(flowerbed)-1):\n",
    "            if  flowerbed[i-1] == 0 and flowerbed[i] == 0 and flowerbed[i+1] == 0:\n",
    "                n = n-1\n",
    "                flowerbed[i] = 1\n",
    "        return n<=0\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        # 找出所有连续0子序列，然后-1/2即得到最大种植数量\n",
    "        segs = [[]]\n",
    "        flowerbed.append(0)\n",
    "        flowerbed.insert(0, 0)\n",
    "        for i in flowerbed:\n",
    "            if i == 0:\n",
    "                segs[-1].append(0)\n",
    "            else: segs.append([])\n",
    "        m = sum([(len(seg)-1)//2 for seg in segs if seg])\n",
    "        return m>=n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\r\n",
    "        #先找到第一朵花在哪\r\n",
    "        first = -1\r\n",
    "        for i in range(len(flowerbed)):\r\n",
    "            if flowerbed[i] == 1:\r\n",
    "                first = i\r\n",
    "                break\r\n",
    "        else:\r\n",
    "            if len(flowerbed)%2 == 0:\r\n",
    "                nmax = len(flowerbed)//2\r\n",
    "            else:\r\n",
    "                nmax = len(flowerbed)//2+1\r\n",
    "            if n <= nmax:\r\n",
    "                return True\r\n",
    "            else:\r\n",
    "                return False\r\n",
    "        list1 = flowerbed[first:]\r\n",
    "        list2 = flowerbed[:first+1]\r\n",
    "        count1 = count2 = 0\r\n",
    "        list2.reverse()\r\n",
    "        for i in range(2,len(list1)):\r\n",
    "            if i == len(list1)-2 and list1[i-1] == 0 and list1[i] == 0 and list1[i+1] == 0:\r\n",
    "                list1[i] = 1\r\n",
    "                count1 += 1\r\n",
    "            elif i == len(list1)-1 and  list1[i-1] == 0 and list1[i] == 0:\r\n",
    "                list1[i] = 1\r\n",
    "                count1 += 1\r\n",
    "            elif list1[i-1] == 0 and list1[i] == 0 and list1[i+1] == 0:\r\n",
    "                list1[i] = 1\r\n",
    "                count1 += 1\r\n",
    "        for i in range(2,len(list2)):\r\n",
    "            if i == len(list2)-2 and list2[i-1] == 0 and list2[i] == 0 and list2[i+1] == 0:\r\n",
    "                list2[i] = 1\r\n",
    "                count2 += 1\r\n",
    "            elif i == len(list2)-1 and list2[i-1] == 0 and list2[i] == 0:\r\n",
    "                list2[i] = 1\r\n",
    "                count2 += 1\r\n",
    "            elif  list2[i-1] == 0 and list2[i] == 0 and list2[i+1] == 0:\r\n",
    "                list2[i] = 1\r\n",
    "                count2 += 1\r\n",
    "        print(count2,count1)\r\n",
    "        return count1 + count2 >= n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        if n==0:\n",
    "            return True\n",
    "        m=len(flowerbed)\n",
    "        for i in range(m):\n",
    "            # 判断当前及左右位置是否种植了花\n",
    "            if flowerbed[i]==1:continue\n",
    "            if i>0 and flowerbed[i-1]==1:continue\n",
    "            if i+1<m and flowerbed[i+1]==1:continue\n",
    "            flowerbed[i]=1\n",
    "            n-=1\n",
    "            if n==0:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, f: List[int], n: int) -> bool:\n",
    "        ans = 0\n",
    "        if len(f) == 0:\n",
    "            return False\n",
    "        if len(f) == 1:\n",
    "            if f[0] == 0:\n",
    "                ans += 1\n",
    "        else:\n",
    "            if f[0]==0 and f[1] == 0:\n",
    "                f[0] = 1\n",
    "                ans +=1\n",
    "            if f[-1] == 0 and f[-2] == 0:\n",
    "                f[-1] = 1\n",
    "                ans += 1\n",
    "\n",
    "            for i in range(1,len(f)-1):\n",
    "                if f[i] == 0 and f[i+1] == 0 and f[i-1] == 0:\n",
    "                    f[i] = 1\n",
    "                    ans+=1\n",
    "        print(f)\n",
    "        return ans>=n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        l = len(flowerbed)\n",
    "        cnt = 0\n",
    "        for i in range(l):\n",
    "            # if cnt == n :\n",
    "            #     break\n",
    "            if flowerbed[i] == 1:\n",
    "                continue\n",
    "            pre = 0 if i == 0 else flowerbed[i-1]\n",
    "            nex = 0 if i == l - 1 else flowerbed[i+1]\n",
    "            if pre == 0 and nex == 0:\n",
    "                cnt += 1\n",
    "                flowerbed[i] = 1\n",
    "        return cnt >= n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        count, m, prev = 0, len(flowerbed), -1\n",
    "        for i in range(m):\n",
    "            if flowerbed[i] == 1:\n",
    "                if prev < 0:\n",
    "                    count += i // 2\n",
    "                else:\n",
    "                    count += (i - prev - 2) // 2\n",
    "                if count >= n:\n",
    "                    return True\n",
    "                prev = i\n",
    "        \n",
    "        if prev < 0:\n",
    "            count += (m + 1) // 2\n",
    "        else:\n",
    "            count += (m - prev - 1) // 2\n",
    "        \n",
    "        return count >= n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        i = 0\n",
    "        while i < len(flowerbed) and n > 0:\n",
    "            if flowerbed[i]== 1:\n",
    "                i += 2\n",
    "            elif i == len(flowerbed) - 1 or flowerbed[i+1] == 0:\n",
    "                n -= 1\n",
    "                i += 2\n",
    "            else:\n",
    "                i += 3\n",
    "\n",
    "            \n",
    "\n",
    "        return (n <= 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        ans = 0\n",
    "        ns = len(flowerbed)\n",
    "        for i in range(ns):\n",
    "            if(i == 0 and not flowerbed[i]):\n",
    "                if(ns > 1 and not flowerbed[i+1]):\n",
    "                    ans += 1\n",
    "                    flowerbed[i] = 1\n",
    "                if(ns == 1):\n",
    "                    ans += 1\n",
    "                    flowerbed[i] = 1\n",
    "            elif(i == ns-1 and not flowerbed[i]):\n",
    "                if(ns > 1 and not flowerbed[i-1]):\n",
    "                    ans += 1\n",
    "                    flowerbed[i] = 1\n",
    "            else:\n",
    "                if(not flowerbed[i] and not flowerbed[i-1] and not flowerbed[i+1]):\n",
    "                    ans += 1\n",
    "                    flowerbed[i] = 1\n",
    "        return ans >= n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        flowerbed = [0] + flowerbed + [0]\n",
    "        num0 = 0\n",
    "        num = 0\n",
    "        for f in flowerbed:\n",
    "            print(f)\n",
    "            if not f:\n",
    "                num0 += 1\n",
    "            else:\n",
    "                num += math.ceil((num0 - 2) / 2)\n",
    "                num0 = 0\n",
    "                if num >= n:\n",
    "                    return True\n",
    "        num += math.ceil((num0 - 2) / 2)\n",
    "        return num >= n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        i, m = 0, len(flowerbed)\n",
    "        while i < m:\n",
    "            if (i == 0 or flowerbed[i-1] == 0) and flowerbed[i] == 0 and (i == m-1 or flowerbed[i+1] == 0):\n",
    "                n -= 1\n",
    "                i += 2\n",
    "            else:\n",
    "                i += 1\n",
    "        return n <= 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        if len(flowerbed)==1:\n",
    "            if flowerbed[0]==0 and n<=1 or flowerbed[0]==1 and n==0:\n",
    "                return True \n",
    "            else:\n",
    "                return False\n",
    "        if flowerbed[0]==0 and flowerbed[1]==0:\n",
    "            num=1\n",
    "            flowerbed[0]=1\n",
    "        else:\n",
    "            num=0\n",
    "        if flowerbed[-2]==0 and flowerbed[-1]==0:\n",
    "            num+=1\n",
    "            flowerbed[-1]=1\n",
    "        for i in range(2,len(flowerbed)-1):\n",
    "            if flowerbed[i-1]==0 and flowerbed[i]==0 and flowerbed[i+1]==0:\n",
    "                flowerbed[i]=1\n",
    "                num+=1\n",
    "        if num>=n:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        num2 = 0\n",
    "        flowerbed = [0] + flowerbed + [0]\n",
    "        for i, j in enumerate(flowerbed):\n",
    "            if flowerbed[i - 1: i + 2] == [0, 0, 0]:\n",
    "                flowerbed[i] = 1\n",
    "                num2 += 1\n",
    "        if num2 >= n:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:\n",
    "        count = 0\n",
    "        for idx in range(len(flowerbed)):\n",
    "            left = 0 if idx - 1 < 0 else flowerbed[idx-1]\n",
    "            right = 0 if idx + 1 > len(flowerbed) - 1 else flowerbed[idx+1]\n",
    "            if not flowerbed[idx] and not left and not right:\n",
    "                count += 1\n",
    "                flowerbed[idx] = 1\n",
    "        return count >= n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
